'''
targetNum = 0
Three number sum
arr = [12, 3, 1, 2, -6, 5, -8, 6]

arr.sort()
                              vR
arr = [-8, -6, 1, 2, 3, 5, 6, 12]
        ^c    ^L

arr[L] + arr[R] = 6 [-6, -6]
'''

def three_number_sum(arr, target_num):
    arr.sort()

    triplets = [] # 三元组

    # 写一个 从 0 到 len(arr) - 3 的循环
    # range(3): 0 1 2
    # range(6): 0 1 2 3 4 5  
    for i in range(len(arr) - 2):
        l = i + 1
        r = len(arr) - 1

        # 找 2 个数字求和
        while l < r:
            current_num = target_num - arr[i]

            if current_num > arr[l] + arr[r]:
                l += 1
            elif current_num < arr[l] + arr[r]:
                r -= 1
            else:
                # 找到了一组答案 arr[i] arr[l] arr[r]
                triplets.append([arr[i], arr[l], arr[r]])
                l += 1
                r -= 1 # 继续在 l r 之间尝试找下一组答案

    return triplets

print(three_number_sum([12, 3, 1, 2, -6, 5, -8, 6], 0))